《剑指offer》 21.调整数组顺序使奇数位于偶数前面

剑指offer
留言

note：数组内凡是需要交换位置的题目，很容易想到双指针的解法，快慢指针、首尾指针都是常见的应用。

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

示例：

1
2
3
输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。

提示：

  • 0 <= nums.length <= 50000
  • 1 <= nums[i] <= 10000

方法一 双指针之快慢指针

思路

常见的快慢指针是行进速度（+1、+2）不同，不过这道题目中快慢指针则是指慢指针有时可以停下来。

这道题归根结底就是让双指针分别指向奇书偶数，如果跑得快的指针指向了奇数，跑的慢的指针指向了偶数，则进行交换。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int slow=0,fast = 0;
        while(fast<nums.size()){
            if(nums[fast]%2==1){
                swap(nums[slow],nums[fast]);
                slow++;
            }
            fast++;
        }
        return nums;
    }
};

复杂度分析

  • 时间复杂度$O(n)$。快指针要依次遍历所有的数
  • 空间复杂度$O(1)$。没有使用额外空间

方法二 双指针之首尾指针

思路

同理，用两个指针找应该进行互换的元素。

不同的在于，我们让首指针去找第一个偶数，找到后不动，让尾指针去找第一个奇数，找到后进行交换，重复上述操作，直到首尾指针相遇。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            if (nums[left]%2==1) {
                left ++;
                continue;
            }
            if (nums[right]%2==0) {
                right --;
                continue;
            }
            swap(nums[left++], nums[right--]);
        }
        return nums;
    }
};

复杂度分析

  • 时间复杂度$O(n)$。同理需要首尾指针遍历完所有的数
  • 空间复杂度$O(1)$。不需要额外的空间。